package chapter3_array;

import java.util.Arrays;

/**
 * 滑动窗口 是从一段开始的 l0 r-1 右边的用于扩大 左边的用于缩小
 * 指针对撞 l0 rr 两面都是缩小 获取一个指定值 一般用于元素有序的情况
 * 操作一个数组时 首先考虑能不能三段考虑 在考虑不能从两面考虑
 */
public class SlideWindow {

    public static void main(String[] args) {
        int[] arr = {1, 4, 4};
        //System.out.println(sliedeWindow(arr, 4));
        String str = "abcccccdesxc";
        System.out.println(getMaxSubLength(str));
    }

    public static int sliedeWindow(int[] nums, int s) {
        if (nums.length == 0) {
            return 0;
        }
        int l = 0, r = 0;
        int length = nums.length + 1;
        while (l <= r && r < nums.length) {
            if (getRangeSum(nums, l, r) >= s) {
                if (r - l + 1 < length) {
                    length = r - l + 1;
                }
                l++;
            } else {
                r++;
            }
        }
        return length > nums.length ? 0 : length;
    }

    public static int getMaxSubLength(String str) {
        boolean[] chars = new boolean[256];
        int l = 0, r = -1;
        int length = 0;
        while (l < str.length()) {
            if (r + 1 < str.length() && !chars[str.charAt(r + 1)]) {
                chars[str.charAt(++r)] = true;
            } else {
                chars[str.charAt(l++)] = false;
            }
            length = Math.max(length, r - l + 1);
        }
        return length;
    }

    public static int lengthOfLongestSubstring(String s) {

        int[] freq = new int[256];

        int l = 0, r = -1; //滑动窗口为s[l...r]
        int res = 0;

        // 整个循环从 l == 0; r == -1 这个空窗口开始
        // 到l == s.size(); r == s.size()-1 这个空窗口截止
        // 在每次循环里逐渐改变窗口, 维护freq, 并记录当前窗口中是否找到了一个新的最优值
        while(l < s.length()){

            if(r + 1 < s.length() && freq[s.charAt(r+1)] == 0)
                freq[s.charAt(++r)] ++;
            else    //r已经到头 || freq[s[r+1]] == 1
                freq[s.charAt(l++)] --;

            res = Math.max(res, r-l+1);
        }

        return res;
    }


    static int getRangeSum(int[] nums, int l, int r) {
        int sum = 0;
        for (int i = l; i <= r; i++) {
            sum += nums[i];
        }
        return sum;
    }
}
